0% completed
Problem Statement
Given an array of integers nums and an integer k, find the starting indices of three non-overlapping subarrays having maximum sum and each of a length k.
Return the array of size 3 containing the starting indices of such subarrays. If multiple answers exist, return the lexicographically smallest answer.
Examples
Example 1:
- Input:
nums = [1, 2, 3, 1, 1, 2, 1, 3, 2], k = 2 - Expected Output:
[1, 4, 7] - Justification: The subarrays would be
[2, 3],[1, 2], and[3, 2]with sums 5, 3, and 5 respectively.
Example 2:
- Input:
nums = [4, 5, 10, 6, 11, 17, 4, 5, 6, 7], k = 3 - Expected Output:
[0, 3, 7] - Justification: The subarrays would be
[4, 5, 10],[6, 11, 17], and[5, 6, 7]with sums 19, 34, and 18 respectively.
Example 3:
- Input:
nums = [1, 1, 1, 1, 1, 1, 1, 1, 1], k = 2 - Expected Output:
[0, 2, 4] - Justification: The subarrays would be
[1, 1],[1, 1], and[1, 1]with each having a sum of 2.
Solution
To solve this problem, we'll utilize dynamic programming. The approach involves breaking down the problem into simpler subproblems, solving each subproblem once, and storing their solutions. We focus on finding the maximum sum for each possible ending position of the first, second, and third subarray. By storing the best possible sums and their corresponding starting indices for the first and second subarrays, we can efficiently calculate the total maximum sum for the third subarray.
This approach is effective because it avoids redundant calculations. Instead of recomputing sums for overlapping sub-problems, we simply refer to previously computed values, greatly reducing the time complexity. Additionally, by keeping track of the indices, we can backtrack to find the exact positions of the subarrays after determining the maximum sum.
Step-by-step Algorithm
-
Initialize Cumulative Sum Array (
sum):- Create an array
sumto store the cumulative sum of thenumsarray. This helps in calculating the sum of any subarray quickly.
- Create an array
-
Calculate Cumulative Sum:
- Iterate over the
numsarray and fill thesumarray such thatsum[i]represents the total sum of the elements fromnums[0]tonums[i-1].
- Iterate over the
-
Initialize
leftArray:- Create an array
leftof the same length asnums. Theleft[i]will store the starting index of the subarray that ends atiand has the maximum sum among all such subarrays.
- Create an array
-
Fill the
leftArray:- Iterate through the
numsarray starting from indexk. For each indexi, calculate the sum of the subarray ending ati(fromi-k+1toi) and updateleft[i]if this subarray has a larger sum than the previous maximum.
- Iterate through the
-
Initialize
rightArray:- Similar to
left, create arightarray. Theright[i]will store the starting index of the subarray that begins atiand has the maximum sum among all such subarrays.
- Similar to
-
Fill the
rightArray:- Iterate through the
numsarray in reverse, starting fromn - k. For each indexi, calculate the sum of the subarray starting atiand updateright[i]if this subarray has a larger sum than the previous maximum.
- Iterate through the
-
Find Maximum Sum of Three Subarrays:
- Iterate over the range
[k, n - 2 * k]and for each indexi, considerias the ending index of the second subarray. The first subarray must end beforeiand the third must start afteri. Useleftandrightarrays to find the starting indices of these subarrays. - Calculate the total sum of these three subarrays. If this total is greater than the previous maximum, update the maximum and store the starting indices of the three subarrays.
- Iterate over the range
-
Return Result:
- After iterating through the entire range, return the stored indices of the three subarrays that give the maximum sum.
Algorithm Walkthrough for Example 1
Using the example nums = [1, 2, 3, 1, 1, 2, 1, 3, 2] and k = 2:
-
Initialize and Calculate Cumulative Sum Array (
sum):sum = [0, 1, 3, 6, 7, 8, 10, 11, 14, 16]- Explanation: Each element in
sumrepresents the cumulative sum up to that index innums.
-
Fill the
leftArray:- Start from index
k = 2. The subarray[1, 2](indices 0 to 1) has a sum of 3. - Move to index 3. The subarray
[2, 3](indices 1 to 2) has a sum of 5, which is greater than 3. Updateleft[3]to 1. - Continue this process. After completion,
leftmight look like[0, 0, 1, 1, 1, 1, 1, 1, 1].
- Start from index
-
Fill the
rightArray:- Start from the end, index
n - k = 7. The subarray[3, 2](indices 7 to 8) has a sum of 5. - Move to index 6. The subarray
[1, 3](indices 6 to 7) has a sum of 4, which is less than 5. Keepright[6]as 7. - Continue in reverse. After completion,
rightmight look like[1, 1, 7, 7, 7, 7, 7, 7, 0].
- Start from the end, index
-
Find Maximum Sum of Three Subarrays:
- Iterate from
i = 2toi = 5(asn - 2 * k = 5).- For
i = 2: Subarrays are [1, 2] (fromleft[1] = 0), [3, 1] (fromnums[2]tonums[3]), and [3, 2] (fromright[4] = 7). Total sum is 12. - For
i = 3: Subarrays are [2, 3], [1, 1] (fromnums[3]tonums[4]), and [3, 2] (fromright[5]). Total sum is 12. - For
i = 4: Subarrays are [2, 3], [1, 2], and [3, 2]. Total sum is 13. This is the maximum sum found so far. - For
i = 5: Subarrays are [1, 2], [2, 1] (fromnums[5]tonums[6]), and [3, 2] (fromright[7]). Total sum is 11.
- For
- Iterate from
-
Result:
- The maximum sum of 13 is achieved with subarrays starting at indices
[1, 4, 7].
- The maximum sum of 13 is achieved with subarrays starting at indices
Code
Complexity Analysis
Time Complexity
- O(n): The algorithm iterates over the array multiple times, where
nis the length of the input array. Despite multiple passes (for cumulative sum, left, right arrays, and finding the maximum sum), each pass is linear, leading to a total time complexity ofO(n).
Space Complexity
- O(n): Additional space is used for the cumulative sum array, left array, and right array, each of size
n. Thus, the total space complexity isO(n), primarily due to these auxiliary data structures.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough for Example 1
Code
Complexity Analysis
Time Complexity
Space Complexity